//! Skip List implementation for Redis-rs2
//! 
//! This module provides a skip list implementation for Redis sorted set operations.
//! For simplicity in this initial implementation, we use a basic approach that will
//! be enhanced with proper concurrent data structures later.

use std::collections::BTreeMap;
use std::cmp::Ordering;

/// A simplified skip list implementation using BTreeMap for sorted storage
/// 
/// This provides the same interface as a full skip list but uses Rust's
/// built-in BTreeMap for the underlying storage. This gives us O(log n)
/// operations while being simpler to implement correctly.
#[derive(Debug, Clone)]
pub struct SkipList<T> {
    /// Internal storage using score as key and values as the data
    /// For values with the same score, we store them in a Vec
    data: BTreeMap<OrderedFloat, Vec<T>>,
    /// Total number of elements
    length: usize,
}

/// Wrapper for f64 that implements Ord for use in BTreeMap
#[derive(Debug, Clone, Copy, PartialEq)]
struct OrderedFloat(f64);

impl Eq for OrderedFloat {}

impl PartialOrd for OrderedFloat {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for OrderedFloat {
    fn cmp(&self, other: &Self) -> Ordering {
        self.0.partial_cmp(&other.0).unwrap_or_else(|| {
            // Handle NaN cases
            if self.0.is_nan() && other.0.is_nan() {
                Ordering::Equal
            } else if self.0.is_nan() {
                Ordering::Greater
            } else {
                Ordering::Less
            }
        })
    }
}

impl From<f64> for OrderedFloat {
    fn from(f: f64) -> Self {
        OrderedFloat(f)
    }
}

/// A node representation for compatibility with the original interface
#[derive(Debug, Clone)]
pub struct SkipListNode<T> {
    pub value: T,
    pub score: f64,
}

impl<T> SkipListNode<T> {
    pub fn new(value: T, score: f64) -> Self {
        Self { value, score }
    }
}

impl<T: Clone + PartialEq + PartialOrd> SkipList<T> {
    /// Create a new empty skip list
    pub fn new() -> Self {
        Self {
            data: BTreeMap::new(),
            length: 0,
        }
    }
    
    /// Insert a new node with the given score and value
    pub fn insert(&mut self, score: f64, value: T) -> bool {
        let key = OrderedFloat::from(score);
        
        // Check if value already exists at this score
        if let Some(values) = self.data.get_mut(&key) {
            if !values.contains(&value) {
                values.push(value);
                values.sort_by(|a, b| a.partial_cmp(b).unwrap_or(Ordering::Equal));
                self.length += 1;
                return true;
            }
            return false; // Value already exists
        }
        
        // Insert new score with this value
        self.data.insert(key, vec![value]);
        self.length += 1;
        true
    }
    
    /// Find a node with the given score and value
    pub fn find(&self, score: f64, value: &T) -> Option<SkipListNode<T>> {
        let key = OrderedFloat::from(score);
        
        if let Some(values) = self.data.get(&key) {
            if values.contains(value) {
                return Some(SkipListNode::new(value.clone(), score));
            }
        }
        
        None
    }
    
    /// Remove a node with the given score and value
    pub fn remove(&mut self, score: f64, value: &T) -> bool {
        let key = OrderedFloat::from(score);
        
        if let Some(values) = self.data.get_mut(&key) {
            if let Some(pos) = values.iter().position(|v| v == value) {
                values.remove(pos);
                self.length -= 1;
                
                // Remove the key if no values left
                if values.is_empty() {
                    self.data.remove(&key);
                }
                
                return true;
            }
        }
        
        false
    }
    
    /// Get all nodes in the given rank range (0-based, inclusive)
    pub fn get_range_by_rank(&self, start: usize, end: usize) -> Vec<SkipListNode<T>> {
        if start >= self.length || start > end {
            return Vec::new();
        }
        
        let mut result = Vec::new();
        let mut index = 0;
        let end = std::cmp::min(end, self.length - 1);
        
        for (score_key, values) in &self.data {
            for value in values {
                if index >= start && index <= end {
                    result.push(SkipListNode::new(value.clone(), score_key.0));
                }
                index += 1;
                if index > end {
                    return result;
                }
            }
        }
        
        result
    }
    
    /// Get all nodes with scores in the given range [min_score, max_score]
    pub fn get_range_by_score(&self, min_score: f64, max_score: f64) -> Vec<SkipListNode<T>> {
        let mut result = Vec::new();
        
        let min_key = OrderedFloat::from(min_score);
        let max_key = OrderedFloat::from(max_score);
        
        for (score_key, values) in self.data.range(min_key..=max_key) {
            for value in values {
                result.push(SkipListNode::new(value.clone(), score_key.0));
            }
        }
        
        result
    }
    
    /// Get the rank (0-based position) of a node with the given score and value
    pub fn get_rank(&self, score: f64, value: &T) -> Option<usize> {
        let mut rank = 0;
        
        for (score_key, values) in &self.data {
            if score_key.0 < score {
                rank += values.len();
            } else if score_key.0 == score {
                if let Some(pos) = values.iter().position(|v| v == value) {
                    return Some(rank + pos);
                }
                return None;
            } else {
                break;
            }
        }
        
        None
    }
    
    /// Get the number of elements in the list
    pub fn len(&self) -> usize {
        self.length
    }
    
    /// Check if the list is empty
    pub fn is_empty(&self) -> bool {
        self.length == 0
    }
    
    /// Get an iterator over all nodes in order
    pub fn iter(&self) -> SkipListIterator<T> {
        let mut nodes = Vec::new();
        
        for (score_key, values) in &self.data {
            for value in values {
                nodes.push(SkipListNode::new(value.clone(), score_key.0));
            }
        }
        
        SkipListIterator {
            nodes: nodes.into_iter(),
        }
    }
}

impl<T: Clone + PartialEq + PartialOrd> Default for SkipList<T> {
    fn default() -> Self {
        Self::new()
    }
}

/// Iterator for skip list nodes
pub struct SkipListIterator<T> {
    nodes: std::vec::IntoIter<SkipListNode<T>>,
}

impl<T> Iterator for SkipListIterator<T> {
    type Item = SkipListNode<T>;
    
    fn next(&mut self) -> Option<Self::Item> {
        self.nodes.next()
    }
}

